class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        TreeNode* rt = root;
        stack<TreeNode*> S;
        vector<int> ans;
        while (rt || !S.empty()) {
            while (rt) {
                S.push(rt);
                rt = rt->left;
            }
            rt = S.top();
            S.pop();
            ans.push_back(rt->val);
            rt = rt->right;
        }
        return ans;
    }
};

